package tests;

import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

public class MinimumSpanningTree {

	Queue<UndirectedGraph.Edge> 	priorityQueue 	= null;
	private final UndirectedGraph 	G;
	
	public MinimumSpanningTree(UndirectedGraph g){
		this.G 		  = g; 
		priorityQueue = new PriorityQueue<UndirectedGraph.Edge>(
							G.getSize(), 
							G.new EdgeComparator());
	}
	
	/* Add each new edge to the priority queue. "New edges" are those edges 
	 * which connect the current node to an unvisited neighbor. */
	private void addNeigborsToPQ(int index, Iterator<UndirectedGraph.Edge> it){
		
		G.setVisited(index);

		/* For each "new edge" of the current node which is 
		 * NOT already on the priority queue...*/
		while(it.hasNext()) {
			UndirectedGraph.Edge nextNeighbor = it.next();			
			if(!priorityQueue.contains(nextNeighbor))
			{
				/* Add the edge to the priority queue. */
				if(!G.getVisited(nextNeighbor.getOppositeVertex(index)))
					priorityQueue.add(nextNeighbor);
			}
		}
	}
	
	/* Run the algorithm from any node in the graph. */
	public double runMST(String startNode) {
		
		double totalDist = 0;
		
		/* Add the startNode's neighbors to the priority queue. */
		System.out.println("Starting MST search from " + startNode);
		int currNodeIndex = G.getVertexIndex(startNode);
		this.addNeigborsToPQ(currNodeIndex, G.getEdgeIterator(currNodeIndex));
		
		/* While there are still valid edges in the priority queue... */ 
		while(!priorityQueue.isEmpty()) {
			System.out.println("The currentNodeIndex: " + currNodeIndex);
			
			/* Pop the lowest weight edge off the PQ. If the "other" 
			 * vertex has not already been visited, then "Move" to it. */
			UndirectedGraph.Edge cheapestEdge = priorityQueue.remove();
			if(!G.getVisited(cheapestEdge.getV()))
				currNodeIndex = cheapestEdge.getV();
			else if(!G.getVisited(cheapestEdge.getW()))
				currNodeIndex = cheapestEdge.getW();
			else{
				System.out.println("MinimumSpanningTree.runMST(): Neither node was unvisited. ");
				continue;
			}
			/* Printout debug information. */
			System.out.print("The cheapest edge on the PQ was " + cheapestEdge.toString());
			System.out.print(" (" + G.getVertexString(cheapestEdge.getV()) + ") |");
			System.out.println(" (" + G.getVertexString(cheapestEdge.getW()) + ")");
			
	
			totalDist += cheapestEdge.getWeight();
			System.out.println("Total Distance: " + totalDist);

			/* Add the neighbors of the NEW current node to the PQ. */
			this.addNeigborsToPQ(currNodeIndex, G.getEdgeIterator(currNodeIndex));
		}
		return totalDist;
	}
}

